package leetcode

//https://leetcode.com/problems/max-consecutive-ones-iii/

/**
 * 使用滑动窗口，让窗口中最多容纳k个0，
 */
fun main(args: Array<String>) {
//    println(findMaxConsecutiveOnesIII(intArrayOf(1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0), 2))
    println(findMaxConsecutiveOnesIII(intArrayOf(0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1), 1))
}

fun findMaxConsecutiveOnesIII(A: IntArray, K: Int): Int {

    var l = 0
    var r = l
    var max = 0
    var zeroCounter = 0

    //如果输入是一个流，可以用一个数组保留k 窗口中每个0的位置
    //等到0溢出的时候，可以直接左移左边界到第二个0的位置
    var zeroPos = Array<Int>(K, { -1 })
    var i = 0
    while (i < A.size) {
        if (A[i] == 0) {
            zeroCounter++
            if (zeroCounter > K) {
                //窗口左边界右移到下一个为0的地方
                while (zeroCounter > K) {
                    if (A[l] == 0) zeroCounter--
                    l++
                }
            }

        }
        r = i
        max = Math.max(max, r - l + 1)
        i++
    }
    return max
}